
import blockengine
import path

class Pathfinding_Grid (blockengine.Grid):    
    def __init__(self, grid_origin, tile_width, tile_height, tile_pixel_size):
        blockengine.Grid.__init__(self, grid_origin, tile_width, tile_height, tile_pixel_size[0], tile_pixel_size[1])
        self.__blocking_tags = []
        self.__astar_max_iterations = 1000
        self.__astar_use_blocking_tiles = True
        self.__astar_end_tile_blocks = True
        
    def getAstar_max_iterations(self):
        return self.__astar_max_iterations
    def setAstar_max_iterations(self, value):
        self.__astar_max_iterations = value
    def delAstar_max_iterations(self):
        del self.__astar_max_iterations        
    def getBlocking_tags(self):
        return self.__blocking_tags
    def setBlocking_tags(self, value):
        self.__blocking_tags = value
    def delBlocking_tags(self):
        del self.__blocking_tags


    def is_tile_blocking (self, tile):
        "true if tile has tags, which are in blocking_tags (so tile blocks)"
        tTags = self.get_objs_for_tag (tile)
        l = [e for e in self.__blocking_tags if e in tTags] 
        if l!=[]:
            return True
        return False
        
    def set_use_blocking_tiles (self, bool):
        self.__astar_use_blocking_tiles = bool
    def set_end_tile_blocks (self, bool):
        self.__astar_end_tile_blocks = bool
        
#    def simple_chase (self, start_tile, end_tile):
#        "find the next free tile between start and end - ignores tags and blockings and stuff"
#        final_path = []     # Resulting path
#        
#        t = start_tile
#        
#        while != end_tile: 
#            if t.rect.tile_x > end_tile:
#                t.
#            
#        
#        heading = self.get_heading_to_target (start_tile.rect.topleft, end_tile)
#        dy = round(math.cos (math.radians(heading)))
#        dx = round(math.sin (math.radians(heading)))
#        
#        
#            x,y = vAdd ((dx,dy), t.rect.tile_topleft)
#            if DEBUG: print heading, dx,dy, (x,y)
#            t = self.get_tile_at_tilepos((int(x), int(y)))
#            tmpc += 1
#        
#            tTags = self.get_objs_for_tag (t)
#            l = [e for e in self.__blocking_tags if e in tTags]
#        
#        
#        return final_path
        
    
    def find_next_free_tile (self, start_tile, end_tile):        
        """
        Uses a simple algo (not Line of sight, simpler) to find a tile which is non-blocking
        in direction of the end_tile (see ai p.8)
        """
        spos = start_tile.rect.tile_topleft
        epos = end_tile.rect.tile_topleft
        pos = list(spos)
        
        while self.is_tile_blocking(self.get_tile_at_tilepos (pos)) == True:
            if epos[0] < pos[0]:
                pos[0] -= 1
            else:
                pos[0] += 1

            if epos[1] < pos[1]:
                pos[1] -= 1
            else:
                pos[1] += 1                
        return self.get_tile_at_tilepos (pos)
         
    def find_path (self, start_tile, end_tile):
        """
        A* Pathfinding
        Returns tuple (true | false, Path-object)
        True: Path calculated, False: something went wrong (no path, blocking etc)
        """
        # Initialize Values       
        tmpc = 0            
        openlist = []       # Tiles to be examinated
        closelist = []      # Tiles already examinated
        final_path = []     # Resulting path
        openlist.append (start_tile)
        
        # find a non-blocking tile in direction of start_tile, if the end_tile is in a blocking space
        if self.__astar_end_tile_blocks == True and self.is_tile_blocking(end_tile) == True:
            end_tile = self.find_next_free_tile (end_tile, start_tile) 
        
        while openlist != [] and tmpc < self.__astar_max_iterations:
            tmpc+=1
            
            # sort openlist for costs
            l = [(li._cost, li) for li in openlist]
            l.sort()
            
            # Get first Tile from Openlist
            tile = l[0][1] 
        
            # Check weather it is the end-tile: then finish
            if tile == end_tile:
                while tile != start_tile:
                    final_path.append(tile)
                    tile = tile.parent
                return (True, path.Path(final_path))
            
            # it is not, so get all neighbours for current tile to examine
            for newtile in self.get_neighbour_tiles(tile):
                if newtile in closelist or newtile in openlist:
                    continue
                
                if self.is_tile_blocking (newtile) == False:
                    newtile.parent = tile
                    # calc step costs - step back to start
                    c = 0
                    t = newtile
                    while t != start_tile:
                        c+=1
                        t = t.parent
                    # calc distance costs as heuristics
                    h = round(self.get_tile_distance(newtile, end_tile),2)
                    newtile._cost = h + c
                    openlist.append(newtile)
            
            # add tile to close list (it has been examinated)
            # and remove from open list
            closelist.append(tile)
            openlist.remove(tile)
            
        #print "WARN: A* END no path found."
        #print "Iterations", tmpc
        return (False, path.Path(final_path))
    
    blocking_tags = property(getBlocking_tags, setBlocking_tags, delBlocking_tags, "Blocking_tags's Docstring")
    astar_max_iterations = property(getAstar_max_iterations, setAstar_max_iterations, delAstar_max_iterations, "Astar_max_iterations's Docstring")





if __name__ == "__main__":
    
    import sys

    def print_grid ():
        # print grid
        print " 0123456789x"
        for y in range (0, g.HTi):
            sys.stdout.write(str(y))
            for x in range (0, g.WTi):
                if g.has_tag (g.get_tile_at_tilepos ((x,y)), "blocking"):
                    sys.stdout.write("X")
                elif g.has_tag (g.get_tile_at_tilepos ((x,y)), "start"):
                    sys.stdout.write("s")
                elif g.has_tag (g.get_tile_at_tilepos ((x,y)), "target"):
                    sys.stdout.write("t")
                elif g.has_tag (g.get_tile_at_tilepos ((x,y)), "path"):
                    sys.stdout.write("i")
                else:
                    sys.stdout.write(".")
            print ""
        print "y"

    def do_test (start, end, block):

        g.flush_register_by_tag ("start")
        g.flush_register_by_tag ("target")
        g.flush_register_by_tag ("blocking")
        g.flush_register_by_tag ("path")
                
        g.register (g.get_tile_at_tilepos(start), "start")
        g.register (g.get_tile_at_tilepos(end), "target")
        
        for b in block:
            g.register (g.get_tile_at_tilepos(b), "blocking") 
        
        p = g.find_path(g.get_tile_at_tilepos(start), g.get_tile_at_tilepos(end) )
        for t in p[1].path:
            g.register (t, "path")
        
        print_grid()

        #g.print_tag_register()
    
    print "Starting unit test !!"
    print "X=blocking"
    print ".=free"
    print "s=start"
    print "t=target"
    print "i=path"
        
    g = Pathfinding_Grid(grid_origin=(0,0), tile_width=12, tile_height=10, tile_pixel_size=(20,20))
    g.blocking_tags = ["blocking"]
    
    print "test: target in blocking area with activated feature end_tile_blocks" 
    start = (9,8)
    end   = (3,2)
    block = ((3,2), (4,2), (3,3), (4,3), (2,1), (3,1), (4,1), (5,1), (2,2), (5,2), (2,3), (5,3), (2,4), (3,4), (4,4), (5,4))

    do_test(start, end, block)

    print "test: target in blocking area with DE-activated feature end_tile_blocks" 
    g.set_end_tile_blocks(False)
    start = (9,8)
    end   = (3,2)
    block = ((3,2), (4,2), (3,3), (4,3), (2,1), (3,1), (4,1), (5,1), (2,2), (5,2), (2,3), (5,3), (2,4), (3,4), (4,4), (5,4))
    
    do_test(start, end, block)
    g.set_end_tile_blocks(True)
        
    print "test: target surrounded by walls"
    start = (9,8)
    end   = (3,2)
    block = ((2,1), (3,1), (4,1), (5,1), (2,2), (5,2), (2,3), (5,3), (2,4), (3,4), (4,4), (5,4))
    
    do_test(start, end, block)
        
    